package leetcode_day._2022._202201._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/20 9:34
 * 石子游戏 IX
 * 算法：博弈论
 * Alice 获胜条件：Bob 移除石子后，移除的石子数量为 3 的倍数
 * Bob 获胜条件：Alice 移除石子后，移除的石子数量为 3 的倍数；石子移除完了
 * 数组元素 %3 后，统计结果为 0 1 2 的数量, 记为 s0, s1, s2
 * 0 是 3 的倍数，1 和 2 不是 3 的倍数，但是 1 + 2 是 3 的倍数
 * 当 s0 为偶数时
 *  s1 = s2 = 0, Alice 输
 *  s1 == 0 || s2 == 0, 如果 s1 = 0, 不管 s2 为多少, Alice 都会输, s2 = 1 或者 2, 石子取完了, s2 = 3, 为 3 的倍数
 *  s1 != 0 && s2 != 0, Alice 赢
 * 当 s0 为奇数时
 *  s1 = s2 = 0, Alice 输
 */
public class _20_2029 {

    public boolean stoneGameIX(int[] stones) {
        int[] cnt = new int[3];
        for (int stone : stones) cnt[stone % 3]++;
        if (cnt[1] == 0 && cnt[2] == 0) return false;
        if (cnt[0] % 2 == 0) return cnt[1] != 0 && cnt[2] != 0;
        else return Math.abs(cnt[1] - cnt[2]) > 2;
    }

}
